package com.demo.algorithms.sort;

/**
 * 堆排序：时间复杂度为O(N*logN)
 * 是指利用堆这种数据结构所设计的一种排序算法。
 * 堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
 * <p>
 * 步骤：
 * 1.将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
 * 2.把堆首（最大值）和堆尾互换；
 * 3.把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
 * 4.重复步骤 2，直到堆的尺寸为 1。
 * <p>
 * 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
 * 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
 * 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
 *
 * @author: 蔡奇峰
 * @date: 2020/7/29 下午4:09
 */
public class HeapSort {

    public static void main(String[] args) {

    }


    /**
     * 堆排序
     *
     * @param arr 要排序的数组（从小到大）
     */
    public static void sort(int[] arr) {



    }

    /**
     * 整合数组为堆结构
     *
     * @param arr   待整合为堆的数组
     * @param start 开始下标
     * @param len   数组长度
     */
    public static void head(int[] arr, int start, int len) {

    }

}
